/*
https://leetcode.cn/problems/maximum-height-by-stacking-cuboids/solutions/2013994/dui-die-chang-fang-ti-de-zui-da-gao-du-b-17qg/
 */
import java.util.Arrays;
import java.util.Comparator;

public class Solution1691 {
    public int maxHeight(int[][] cuboids) {
        for (int[] cuboid : cuboids) {
            Arrays.sort(cuboid);
        }
        Arrays.sort(cuboids, Comparator.comparingInt(a -> (a[0] + a[1] + a[2])));
        int[] f=new int[cuboids.length];
        for (int i=0;i<cuboids.length;i++){
            f[i]=cuboids[i][2];
            for (int j=0;j<i;j++){
                if (cuboids[i][0]>=cuboids[j][0] && cuboids[i][1]>=cuboids[j][1] && cuboids[i][2]>=cuboids[j][2]){
                    f[i]=Math.max(f[i],f[j]+cuboids[i][2]);
                }
            }
        }
        return Arrays.stream(f).max().getAsInt();
    }

    public static void main(String[] args) {
        System.out.println(new Solution1691().maxHeight(new int[][]{{50,45,20},{95,37,53},{45,23,12}}));
    }
}
